The present invention relates to computer graphics, and more particularly to cellular automata application programs in the context of computer graphics.
A cellular automata program, or simply a xe2x80x9ccellular automata,xe2x80x9d is a program in which a set of rules is applied to a discreet array or grid of values in order to create a new value at each point in the grid. Each grid value is a xe2x80x9ccellxe2x80x9d and the state of the grid constitutes one xe2x80x9cgenerationxe2x80x9d of the field of cells. In applying the rules to a generation, a new generation of cells is created. The rules are then applied to the new generation to create yet another, and so forth.
Typically, the rules are local to each cell of the grid, meaning they involve only the cells surrounding each individual cell. One example of such a rule includes: xe2x80x9cturn a cell on if it has exactly three neighbors that are also turned onxe2x80x9d and xe2x80x9cturn a cell off if it has more than three neighbors turned on.xe2x80x9d This simplifies the creation of each new generation, as only a small area of the previous generation determines the state of each new cell.
Cellular automata programs are typically run on a 2-dimensional (2D) grid, but can also be specified in n-dimensions. The programs produce useful and interesting patterns as they evolve over time. In the context of computer graphics, the patterns are useful in rendering animated effects and for generating features procedurally.
An example of the foregoing principles will now be set forth in the context of computer graphics. Such example involves combining neighbor sampling and dependent lookups to run Conway""s popular xe2x80x9cGame of Lifexe2x80x9d cellular automata programming in a graphics pipeline. For more information on such program reference may be made to: Gardner, Martin, xe2x80x9cMathematical Games,xe2x80x9d Scientific American, vol. 223, no. 4, Octobre 1970, pp. 120-123; which is incorporated herein by reference in its entirety. While the present example involves Conway""scellular automata formulation, modifications may be applied to run significantly more complex cellular automata programs.
In Conway""sxe2x80x9cGame of Life,xe2x80x9d each cell begins as either xe2x80x9conxe2x80x9d or xe2x80x9coffxe2x80x9d which is represented by a grid of white or black texels, respectively. The rules for creating the next generation for every cell on the map are shown in Table #1.
The game requires that for each cell, the eight cell neighbors and the cell itself be sampled, and logic be applied to the result of the sampling. More information on an exemplary technique for running the game using a hardware stencil buffer may be found with reference to: Neider, Jackie, et. al., OpenGL Programming Guide, Addison-Wesley Publishing Co., 1993.
Prior Art FIG. 1 illustrates an exemplary rule table 100 that may be used by a cellular automata program. As shown, the rule table 100 embodies the rules of Table #1, and may be used to carry out the foregoing logic necessary for creation of the next generation of cells. The rule table 100 is accessed for each cell at a horizontal coordinate according to the number from zero to eight of neighbors which are xe2x80x9conxe2x80x9d and in the vertical coordinate according to whether the cell is xe2x80x9conxe2x80x9d or xe2x80x9coff.xe2x80x9d The table yields an xe2x80x9cXxe2x80x9d for all cells conditions that should result in an xe2x80x9conxe2x80x9d cell in the next generation and is blank for all cell conditions that should result in a xe2x80x9coffxe2x80x9d cell.
Prior Art FIG. 2 illustrates an example of how a first cell state 200 may be translated into a second cell state 202 based on the logic embodied in the rule map 100 of FIG. 1. Prior Art FIG. 3 shows a more intricate example 300 of how a cellular automata program may operate based on the logic embodied in the rule map 100 of FIG. 1 and yield various patterns over six generations of cells. Application of the rules to each numbered generation results in the subsequent numbered generation.
As mentioned earlier, the foregoing patterns are useful in the context of computer graphics rendering. Traditionally, such cellular automata programs have been implemented on general central processing unit (CPU) architectures utilizing software and a system-to-video card bus or in a limited and inflexible manner using a hardware stencil buffer. Such systems are typically limited in speed and bandwidth. There is thus a need for the ability to run such programs efficiently on a hardware graphics pipeline, avoid a transfer of data across a system-to-graphics pipeline bus, and establish a technique by which the rules that govern the cellular automata may be easily changed.
A system and method are provided for executing a cellular automata program in a hardware graphics pipeline. Initially, cell values are received in a hardware graphics pipeline. Next, the cell values are rendered to generate a condition value utilizing the hardware graphics pipeline. A cell value result for the subsequent generation is read from a rule map according to the condition value utilizing the hardware graphics pipeline. Still yet, additional cell values are stored based on the rule map value.
In one embodiment, the cell values may be referenced by geometry. As an option, the cell values may be referenced as an array of textures.
In another embodiment, a plurality of the cell values may be combined. Further, the combined cell values may be rendered to generate the condition value. Optionally, at least one of the combined cell values may include a cell value from a previous iteration of the receiving, rendering, and reading operations.
In still another embodiment, the condition value may be represented by a color value. In use, a plurality of the condition values may be combined. Moreover, the rule map value may be read from the rule map with the combined condition values.
In still yet another embodiment, the rule map may be 1-dimensional, 2-dimensional, 3-dimensional, 4-dimensional, etc. Further, the rule map may be a look-up table. In use, the rule map value may be read from the rule map utilizing the condition value as an index into the rule map. Optionally, the rule map value may be programmably read from the rule map.
As an option, a plurality of rule map values may be read from a plurality of rule maps. Further, the receiving, rendering, and reading operations may be repeated in multiple iterations utilizing the rule map value from a previous iteration.
In still another embodiment, the receiving, rendering, and reading operations may be repeated in multiple iterations. Such operations may further be programmably repeated. Such programmability may be applied to any desired aspect of the present embodiment.
In another embodiment, the geometry referencing the cell values may be bound to the rule map. Further, the geometry may be bound to information indicating how to access a plurality of the cell values as a texture lookup. While any desired architecture may be used in the context of the present embodiment, the various operations may be executed in a multi-texture engine of the hardware graphics pipeline.
Optionally, the cell values may be written to the rule map itself in the hardware graphics pipeline, thereby creating a self-modifying cellular automata program.
These and other advantages of the present invention will become apparent upon reading the following detailed description and studying the various figures of the drawings.